Algorithm
Problem Name:
In this HackerRank Functions in Java programming problem solution,
We define the following:
- A subarray of an n-element array is an array composed from a contiguous block of the original array's elements. For example, if array = [1,2,3], then the subarrays are [1], [2], [3], [1,2], [2,3], [1,2,3]. Something like [1,3] would not be a subarray as it's not a contiguous subsection of the original array.
- The sum of an array is the total sum of its elements.
- An array's sum is negative if the total sum of its elements is negative.
- An array's sum is positive if the total sum of its elements is positive.
Given an array of n integers, find and print its number of negative subarrays on a new line.
Input Format
The first line contains a single integer, n, denoting the length of array A = [a0, a1,...,an-1].
The second line contains n space-separated integers describing each respective element, ai , in array A.
Constraints
- 1 <= n <= 100
- -10**4 <= ai <= 10**4
Output Format
Print the number of subarrays of A having negative sums.
Sample Input
5
1 -2 4 -5 1
Sample Output
9
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
import java.util.Scanner;
// A subarray must be contiguous. There are O(n^2) contiguous subarrays.
// Time Complexity: O(n^2)
// Space Complexity: O(1)
public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int size = scan.nextInt();
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = scan.nextInt();
}
scan.close();
System.out.println(negativeSubarrays(array));
}
private static int negativeSubarrays(int[] array) {
int count = 0;
for (int i = 0; i < array.length; i++) {
int sum = 0;
for (int j = i; j < array.length; j++) {
sum += array[j];
if (sum < 0) {
count++;
}
}
}
return count;
}
}